package leetcode.tree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import datastructure.binarytree.TreeNode;

public class LeetCode297Level {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return null;
        }
        StringBuilder sb = new StringBuilder();
        level(root, sb);
        return sb.substring(1).toString();
   }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null) {
            return null;
        }
        List<String> list = new LinkedList<>(Arrays.asList(data.split(",")));
        if (list == null || list.isEmpty()) {
            return null;
        }
        return level(list);
    }
   

   private TreeNode level(List<String> list) {
        String first = list.remove(0);
        if ("null".equals(first)) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(first));
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty() && !list.isEmpty()) {
            TreeNode n = q.poll();
            String val = list.remove(0);
            if (!"null".equals(val)) {
                n.left = new TreeNode(Integer.valueOf(val));
                q.offer(n.left);
            }
            val = list.remove(0);
            if (!"null".equals(val)) {
                n.right = new TreeNode(Integer.valueOf(val));
                q.offer(n.right);
            }
        }
        return root;
    }

    // public static void level(TreeNode root, StringBuilder sb) {
    //     Queue<TreeNode> q = new LinkedList<>();
    //     q.add(root);
    //     while (!q.isEmpty()) {
    //         TreeNode n = q.poll();
    //         if (n == null) {
    //             sb.append(",null");
    //             continue;
    //         }
    //         sb.append("," + n.val);
    //         if (n.left != null) {
    //             q.offer(n.left);
    //         } else {
    //             q.offer(null);
    //         }
    //         if (n.right != null) {
    //             q.offer(n.right);
    //         } else {
    //             q.offer(null);
    //         }
    //     }
    // }

    public static void level(TreeNode root, StringBuilder sb) {
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int level = 1;
        while (!q.isEmpty()) {
            int qSize = q.size();
            // System.out.println("queue size:" + qSize);
            // for 循环不是必须的，可以移除，这里是为了记录当前层的步数
            for (int i = 0; i < qSize; i++) {
                // System.out.println("当前在第" + level +"层的第" + (i + 1) + "步");
                TreeNode n = q.poll();
                if (n == null) {
                    sb.append(",null");
                    continue;
                }
                sb.append("," + n.val);
                if (n.left != null) {
                    q.offer(n.left);
                } else {
                    q.offer(null);
                }
                if (n.right != null) {
                    q.offer(n.right);
                } else {
                    q.offer(null);
                }
            }
            level++;
           
        }
    }
}